package leetcode_周赛._2023._11;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 第 373 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/11/26 19:27
 */
public class _26 {

    /**
     * 2948.交换得到字典序最小的数组
     * 算法: 分组排序
     * 时间复杂度: (nlogn)
     * 5, 4, 3, 2, 1 的字典序最小的数组 1, 2, 3, 4, 5
     * 只要连续相邻元素的差值为 limit, 那么这组元素就可以排序
     */
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        int[][] g = new int[n][2];
        for (int i = 0; i < n; i++) {
            g[i][0] = nums[i];
            g[i][1] = i;
        }
        Arrays.sort(g, Comparator.comparing(a -> a[0]));
        int[] idxs = new int[n];
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n && g[j][0] - g[j - 1][0] <= limit) ++j;
            for (int k = i; k < j; k++) idxs[k] = g[k][1];
            Arrays.sort(idxs, i, j);
            for (int k = i; k < j; k++) nums[idxs[k]] = g[k][0];
            i = j;
        }
        return nums;
    }

}
